package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
	"time"
)

// 大数据得要个好电脑 8G内存  一跑就没有内存
// 10

type qq struct {
	qqNum  int
	qqPass string
}

//优化快速排序
/**
数据载入内存
开始排序
执行排序的时间 18.3714219s
请输入要查询的数据
438905700
36403652 438905700 320675
一共用了 93.0012ms   未使用二分查找
请输入要查询的数据
438905700
36403652 438905700 320675
一共用了 63.9983ms
请输入要查询的数据

// 使用二分查找  一共用了 14.994ms

*/
func QuickSort7(left int, right int, arr []qq) {

	l := left
	r := right
	// pivot 是中轴， 支点
	pivot := arr[(left+right)/2]
	temp := pivot

	//for 循环的目标是将比 pivot 小的数放到 左边
	//  比 pivot 大的数放到 右边
	for l < r {
		//从  pivot 的左边找到大于等于pivot的值
		for arr[l].qqNum < pivot.qqNum {
			l++
		}
		//从  pivot 的右边边找到小于等于pivot的值
		for arr[r].qqNum > pivot.qqNum {
			r--
		}
		// 1 >= r 表明本次分解任务完成, break
		if l >= r {
			break
		}
		//交换
		temp = arr[l]
		arr[l] = arr[r]
		arr[r] = temp
		//优化
		if arr[l].qqNum == pivot.qqNum {
			r--
		}
		if arr[r].qqNum == pivot.qqNum {
			l++
		}
	}

	// fmt.Println("第一次数组排序", array)

	// 如果  1== r, 再移动下
	if l == r {
		l++
		r--
	}
	// 向左递归
	if left < r {
		QuickSort7(left, r, arr)
	}
	// 向右递归
	if right > l {
		QuickSort7(l, right, arr)
	}
}

// 排序内存爆表  84331445条数据
// 无法排序成功
func QuickSort6(arr []qq) []qq {

	length := len(arr)
	if length <= 1 {
		return arr //只有一元素无需排序
	} else {
		splitdata := arr[0] //第一个数字
		low := make([]qq, 0, 0)
		high := make([]qq, 0, 0)
		mid := make([]qq, 0, 0)
		mid = append(mid, splitdata) //保存分离的数据
		//数据分为三段处理，分别是大于，等于，小于
		for i := 1; i < length; i++ {
			if arr[i].qqNum < splitdata.qqNum {
				low = append(low, arr[i])
			} else if arr[i].qqNum > splitdata.qqNum {
				high = append(high, arr[i])
			} else {
				mid = append(mid, arr[i])
			}
		}
		low, high = QuickSort6(low), QuickSort6(high) //递归循环
		myarr := append(append(low, mid...), high...) //数据归并
		return myarr

	}
}

func bin_searchX(arr []qq, data int) int {
	left := 0
	right := len(arr) - 1 //最下最上面
	for left <= right {
		mid := (left + right) / 2
		// fmt.Println(mid, "===", left, right)
		if arr[mid].qqNum > data {
			right = mid - 1
		} else if arr[mid].qqNum < data {
			left = mid + 1 //移动
		} else {
			return mid //找到
		}
	}
	return -1
}

func main() {

	count := 84331445

	allstrs := make([]qq, count) //初始化数组
	path := "D:\\golang\\QQ.txt"
	qqfile, _ := os.Open(path) //打开文件
	defer qqfile.Close()       // 延迟关闭

	bf := bufio.NewReader(qqfile) // 读取数据
	i := 0

	for {
		line, _, err := bf.ReadLine() //读取一样文件

		if err == io.EOF { //读取到文件的最后一样
			break
		}

		linestr := string(line) //转化成字符串
		arrStr := strings.Split(linestr, "----")
		if len(arrStr) == 2 {
			allstrs[i].qqNum, _ = strconv.Atoi(arrStr[0])
			allstrs[i].qqPass = arrStr[1]
		}

		i++
	}
	fmt.Println("数据载入内存")
	time.Sleep(time.Second * 1)

	fmt.Println("开始排序 数据长度：", len(allstrs))

	t1 := time.Now()
	// allstrs = QuickSort6(allstrs)  //太多变量  消耗大量内存
	QuickSort7(0, len(allstrs)-1, allstrs)
	fmt.Println("执行排序的时间", time.Since(t1))

	for {
		fmt.Println("请输入要查询的数据")
		var inputstr int
		fmt.Scanln(&inputstr)

		starttime := time.Now() //时间开始
		/**   普通查找   63.9983ms
		for j := 0; j < count; j++ {

			if allstrs[j].qqNum == inputstr { //字符串搜索
				fmt.Println(j, allstrs[j].qqNum, allstrs[j].qqPass)
				break
			}
		}
		*/

		// 使用二分查找  一共用了 14.994ms

		index := bin_searchX(allstrs, inputstr)
		if index == -1 {
			fmt.Println("未找到")
		} else {
			fmt.Println(index, "QQ号码：", allstrs[index].qqNum, "qq密码", allstrs[index].qqPass)
		}

		fmt.Println("一共用了", time.Since(starttime))
	}

}
